{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Population Year"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumPopulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #人口最多的年份"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二维整数数组 <code>logs</code> ，其中每个 <code>logs[i] = [birth<sub>i</sub>, death<sub>i</sub>]</code> 表示第 <code>i</code> 个人的出生和死亡年份。</p>\n",
    "\n",
    "<p>年份 <code>x</code> 的 <strong>人口</strong> 定义为这一年期间活着的人的数目。第 <code>i</code> 个人被计入年份 <code>x</code> 的人口需要满足：<code>x</code> 在闭区间 <code>[birth<sub>i</sub>, death<sub>i</sub> - 1]</code> 内。注意，人不应当计入他们死亡当年的人口中。</p>\n",
    "\n",
    "<p>返回 <strong>人口最多</strong> 且 <strong>最早</strong> 的年份。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>logs = [[1993,1999],[2000,2010]]\n",
    "<strong>输出：</strong>1993\n",
    "<strong>解释：</strong>人口最多为 1 ，而 1993 是人口为 1 的最早年份。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>logs = [[1950,1961],[1960,1971],[1970,1981]]\n",
    "<strong>输出：</strong>1960\n",
    "<strong>解释：</strong> \n",
    "人口最多为 2 ，分别出现在 1960 和 1970 。\n",
    "其中最早年份是 1960 。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= logs.length &lt;= 100</code></li>\n",
    "\t<li><code>1950 &lt;= birth<sub>i</sub> &lt; death<sub>i</sub> &lt;= 2050</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-population-year](https://leetcode.cn/problems/maximum-population-year/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-population-year](https://leetcode.cn/problems/maximum-population-year/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1993,1999],[2000,2010]]', '[[1950,1961],[1960,1971],[1970,1981]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import reduce\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        #min_year = reduce(lambda x: min(x[0]), logs)\n",
    "        #max_year = reduce(lambda x: max(x[1]), logs)\n",
    "\n",
    "        year_lst = [x for _ in logs for x in _]\n",
    "        year_lst = sorted(set(year_lst))\n",
    "        print(year_lst)\n",
    "        d = {}\n",
    "        for x in year_lst:\n",
    "            for y in logs:\n",
    "                if x in range(y[0], y[1]):\n",
    "                    d[x] = d.get(x, 0) + 1\n",
    "        \n",
    "        return max(d, key = d.get)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        m = {}\n",
    "        maximum = 0\n",
    "        for log in logs:\n",
    "            for year in range(log[0], log[1]):\n",
    "                if year not in m.keys():\n",
    "                    m[year] = 1\n",
    "                else:\n",
    "                    m[year] += 1\n",
    "                maximum = max(maximum, m[year])\n",
    "        # sm = sorted(m.items(), key=lambda row: row[1], reverse=True)\n",
    "        # print(\"m=\", m)\n",
    "        years = [key for key in m.keys() if m[key] == maximum]\n",
    "        return min(years)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        a=[0]*100\n",
    "        for i,j in logs:\n",
    "            for k in range(i,j):\n",
    "                a[k-1950]+=1\n",
    "        return a.index(max(a))+1950\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        delta = [0] * 101   # 变化量\n",
    "        offset = 1950   # 起始年份与起始下标之差\n",
    "        for b, d in logs:\n",
    "            delta[b-offset] += 1\n",
    "            delta[d-offset] -= 1\n",
    "        mx = 0   # 人口数量最大值\n",
    "        res = 0   # 最大值对应的最小下标\n",
    "        curr = 0   # 每一年的人口数量\n",
    "        # 前缀和\n",
    "        for i in range(101):\n",
    "            curr += delta[i]\n",
    "            if curr > mx:\n",
    "                mx = curr\n",
    "                res = i\n",
    "        return res + offset   # 转回对应的年份\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        dates=[]\n",
    "        for birth,death in logs:\n",
    "            dates.append((birth,1))\n",
    "            dates.append((death,-1))\n",
    "\n",
    "        dates.sort()\n",
    "        population=max_population=max_year=0\n",
    "        for year,change in dates:\n",
    "            population+=change\n",
    "            if population>max_population:\n",
    "                max_population=population\n",
    "                max_year=year\n",
    "\n",
    "        return max_year"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        arr = [0] * (2050 - 1950 + 1)\n",
    "        for b, d in logs:\n",
    "            for i in range(b - 1950, d - 1950):\n",
    "                arr[i] += 1\n",
    "        mx = max(arr)\n",
    "        for i, x in enumerate(arr):\n",
    "            if x == mx:\n",
    "                return 1950 + i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        population = [0] * 10001\n",
    "        for log in logs:\n",
    "            birth, death = log[0], log[1]\n",
    "            population[birth] += 1\n",
    "            population[death] -= 1\n",
    "\n",
    "        max_population = population[0]\n",
    "        earliest_year = 0\n",
    "        curr_population = population[0]\n",
    "\n",
    "        for i in range(1, 10001):\n",
    "            curr_population += population[i]\n",
    "            if curr_population > max_population:\n",
    "                max_population = curr_population\n",
    "                earliest_year = i\n",
    "\n",
    "        return earliest_year"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        delta = [0] * 101   # 变化量\n",
    "        offset = 1950   # 起始年份与起始下标之差\n",
    "        for b, d in logs:\n",
    "            delta[b-offset] += 1\n",
    "            delta[d-offset] -= 1\n",
    "        mx = 0   # 人口数量最大值\n",
    "        res = 0   # 最大值对应的最小下标\n",
    "        curr = 0   # 每一年的人口数量\n",
    "        # 前缀和\n",
    "        for i in range(101):\n",
    "            curr += delta[i]\n",
    "            if curr > mx:\n",
    "                mx = curr\n",
    "                res = i\n",
    "        return res + offset   # 转回对应的年份\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        counts=defaultdict(int)\n",
    "        for log in logs:\n",
    "            for year in range(*log):\n",
    "                counts[year]+=1\n",
    "        ans=inf\n",
    "        for year in counts:\n",
    "            if counts[year]==max(counts.values()):\n",
    "                ans=min(ans,year)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        maxCnt = 0\n",
    "        for year in range(1950, 2051):\n",
    "            cnt = 0\n",
    "            for log in logs:\n",
    "                if log[0] <= year < log[1]:\n",
    "                    cnt += 1\n",
    "                if cnt > maxCnt:\n",
    "                    maxCnt = cnt\n",
    "                    ans = year\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        count_list = [0] * 101\n",
    "        offset = 1950\n",
    "        for birth, death in logs:\n",
    "            count_list[birth - offset] += 1\n",
    "            count_list[death - offset] -= 1\n",
    "        max_count = max_year = 0\n",
    "        current_count = 0\n",
    "        for year in range(len(count_list)):\n",
    "            current_count += count_list[year]\n",
    "            if current_count > max_count:\n",
    "                max_count = current_count\n",
    "                max_year = year\n",
    "        return max_year + offset\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        num, res = 0, 0\n",
    "        dic = {}\n",
    "        for i,j in logs:\n",
    "            for k in range(i,j):\n",
    "                if k in dic:\n",
    "                    dic[k] += 1\n",
    "                else:\n",
    "                    dic[k] = 1\n",
    "                if dic[k] > num:\n",
    "                    res, num = k, dic[k]\n",
    "                elif dic[k] == num and res > k:\n",
    "                    res = k\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        delta = [0] * 101   # 变化量\n",
    "        offset = 1950   # 起始年份与起始下标之差\n",
    "        for b, d in logs:\n",
    "            delta[b-offset] += 1\n",
    "            delta[d-offset] -= 1\n",
    "        mx = 0   # 人口数量最大值\n",
    "        res = 0   # 最大值对应的最小下标\n",
    "        curr = 0   # 每一年的人口数量\n",
    "        # 前缀和\n",
    "        for i in range(101):\n",
    "            curr += delta[i]\n",
    "            if curr > mx:\n",
    "                mx = curr\n",
    "                res = i\n",
    "        return res + offset   # 转回对应的年份\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        dates = []\n",
    "        for birth,death in logs:\n",
    "            dates.append((birth,1))\n",
    "            dates.append((death,-1))\n",
    "        dates.sort()\n",
    "        popilation = max_popultion = max_year = 0\n",
    "        for year,change in dates:\n",
    "            popilation += change\n",
    "            if popilation > max_popultion:\n",
    "                max_popultion = popilation\n",
    "                max_year = year\n",
    "        return max_year"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        people=[0]*101\n",
    "        baseYear=1950\n",
    "        for birth,death in logs:\n",
    "            people[birth-baseYear]+=1\n",
    "            people[death-baseYear]-=1\n",
    "        # 人口数量最大值\n",
    "        maxnum=0\n",
    "        # 最大值对应的下标\n",
    "        res=0\n",
    "        # 每年的人口数量\n",
    "        cur=0\n",
    "        for i in range(101):\n",
    "            cur+=people[i]\n",
    "            if cur>maxnum:\n",
    "                maxnum=cur\n",
    "                res=i\n",
    "        return res+baseYear\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        min_y = 1000\n",
    "        max_y = 0\n",
    "        for log in logs:\n",
    "            min_y = min(min_y, log[0])\n",
    "            max_y = max(max_y, log[1])\n",
    "\n",
    "        delta = [0] *101\n",
    "        offset =1950\n",
    "        for b, d in logs:\n",
    "            delta[b-offset] +=1\n",
    "            delta[d-offset] -=1\n",
    "        mx = 0\n",
    "        res = 0\n",
    "        curr = 0\n",
    "        for i in range(101):\n",
    "            curr += delta[i]\n",
    "            if curr >mx:\n",
    "                mx = curr\n",
    "                res = i\n",
    "        return res +offset\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        if len(logs) == 1:\n",
    "            return logs[0][0]\n",
    "\n",
    "        res = logs[0][0]\n",
    "        logs = sorted(logs, key = lambda x: x[0], reverse = True) \n",
    "\n",
    "        cnt, ans = 0, 0\n",
    "        for i in range(len(logs) - 1):\n",
    "            for  j in range(i+1, len(logs)):\n",
    "                if logs[i][0] >= logs[j][0] and logs[i][0] < logs[j][1]:\n",
    "                    cnt += 1\n",
    "                    \n",
    "            if cnt and cnt >= ans:\n",
    "                ans = cnt\n",
    "                res = logs[i][0]\n",
    "            cnt = 0\n",
    "\n",
    "        return res if ans else min(logs[-1][0], res)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        events = []\n",
    "        for s, e in logs:\n",
    "            events.append([s, 1])\n",
    "            events.append([e, -1])\n",
    "        events.sort()\n",
    "\n",
    "        res, count, maxCount = 0, 0, 0\n",
    "        for year, sign in events:\n",
    "            if sign == 1:\n",
    "                count += 1\n",
    "                if count > maxCount:\n",
    "                    res = year\n",
    "                    maxCount = count  \n",
    "            else:\n",
    "                count -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        delta = [0] * 101   \n",
    "        offset = 1950   \n",
    "        for b, d in logs:\n",
    "            delta[b-offset] += 1\n",
    "            delta[d-offset] -= 1\n",
    "        mx = 0   \n",
    "        res = 0   \n",
    "        curr = 0  \n",
    "        \n",
    "        for i in range(101):\n",
    "            curr += delta[i]\n",
    "            if curr > mx:\n",
    "                mx = curr\n",
    "                res = i\n",
    "        return res + offset   \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        p = [0] * 101\n",
    "        for start, end in logs:\n",
    "            p[start-1950] += 1\n",
    "            p[end-1950] -= 1\n",
    "        mx = ans = 0\n",
    "        for i, n in enumerate(accumulate(p)):\n",
    "            if n > mx:\n",
    "                mx, ans = n, i\n",
    "        return ans + 1950"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        l1 = []\n",
    "        for i in range (len(logs)):\n",
    "            l1.append(logs[i][0])\n",
    "            l1.append(logs[i][1])\n",
    "        x1 = min(l1)\n",
    "        x2 = max(l1)\n",
    "        l2 = [0] * (x2 - x1)\n",
    "        for i in range (len(logs)):\n",
    "            for k in range (logs[i][0] - x1, logs[i][1] - x1):\n",
    "                l2[k] += 1\n",
    "        return l2.index(max(l2)) + x1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        p = [0] * 100\n",
    "        for start, end in logs:\n",
    "            for i in range(start-1950, end-1950):\n",
    "                p[i] += 1\n",
    "        return p.index(max(p)) + 1950"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        num, res = 0, 0\n",
    "        dic = {}\n",
    "        for i,j in logs:\n",
    "            for k in range(i,j):\n",
    "                if k in dic:\n",
    "                    dic[k] += 1\n",
    "                else:\n",
    "                    dic[k] = 1\n",
    "                if dic[k] > num:\n",
    "                    res, num = k, dic[k]\n",
    "                elif dic[k] == num and res > k:\n",
    "                    res = k\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        dates = []\n",
    "        for birth, death in logs:\n",
    "            dates.append((birth, 1))\n",
    "            dates.append((death, -1))\n",
    "            \n",
    "        dates.sort()\n",
    "        population = max_population = max_year = 0\n",
    "        for year, change in dates:\n",
    "            population += change\n",
    "            if population > max_population:\n",
    "                max_population = population\n",
    "                max_year = year\n",
    "        \n",
    "        return max_year"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        lst = [0] * 101\n",
    "        for a, b in logs:\n",
    "            lst[a - 1950] += 1\n",
    "            lst[b - 1950] -= 1\n",
    "        ans, m, cur = 0, 0, 0\n",
    "        for i, n in enumerate(lst):\n",
    "            cur += n\n",
    "            if cur > m:\n",
    "                m = cur\n",
    "                ans = i\n",
    "        return ans + 1950"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        logs=sorted(logs)\n",
    "        dic=defaultdict(int)\n",
    "        for s,d in logs:\n",
    "            dic[s]+=1\n",
    "            dic[d]-=1\n",
    "\n",
    "        mx,ans=0,-1\n",
    "        cnt=0\n",
    "        for year in sorted(dic.keys()):\n",
    "            cnt+=dic[year]\n",
    "            if cnt>mx:\n",
    "                mx=cnt\n",
    "                ans=year\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        lis = [0] * 101\n",
    "        change_max = 0\n",
    "        change = 0\n",
    "        earliest_year = 0\n",
    "        for i in logs:\n",
    "            lis[i[0]-1950] += 1\n",
    "            lis[i[1]-1950] -= 1\n",
    "        for i in range(100):\n",
    "            change += lis[i]\n",
    "            if change > change_max:\n",
    "                change_max = change\n",
    "                earliest_year = i + 1950\n",
    "        return earliest_year\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs):\n",
    "        li = [0] * 101\n",
    "        for i in logs:\n",
    "            birth = i[0] - 1950\n",
    "            death = i[1] - 1950\n",
    "            if birth == death:\n",
    "                continue\n",
    "            else:\n",
    "                for j in range(birth, death):\n",
    "                    li[j] += 1\n",
    "        ma = float(\"-inf\")\n",
    "        min_year = logs[0][0]\n",
    "        for i in range(len(li)):\n",
    "            if li[i]>ma:\n",
    "                ma = li[i]\n",
    "                min_year = i+1950\n",
    "        return min_year\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        delta = [0]*101\n",
    "        offset = 1950\n",
    "        for b,d in logs:\n",
    "            delta[b-offset] +=1\n",
    "            delta[d-offset] -=1\n",
    "        mx=0\n",
    "        res=0\n",
    "        curr=0\n",
    "        for i in range(101):\n",
    "            curr+=delta[i]\n",
    "            if curr>mx:\n",
    "                mx=curr\n",
    "                res=i\n",
    "        return res+offset\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        dp = [0] * 2050\n",
    "        for l in logs:\n",
    "            for i in range(l[0],l[1]):\n",
    "                dp[i] += 1\n",
    "        return dp[1950:].index(max(dp[1950:])) + 1950\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        ad={}\n",
    "        for i in logs:\n",
    "            for j in range(i[0],i[1]):\n",
    "                ad[j]=ad.get(j,0)+1\n",
    "        r=[[k,v] for k,v in ad.items()]\n",
    "        r.sort(key=lambda x:(x[1]))\n",
    "        rr=[x for x in ad if ad[x]==r[-1][1]]\n",
    "        rr.sort()\n",
    "        return rr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        year = [0] * (2050-1950+1)\n",
    "        for b, d in logs:\n",
    "            year[b-1950] += 1\n",
    "            year[d-1950] -= 1\n",
    "\n",
    "        cnt = 0\n",
    "        max_cnt = 0\n",
    "        ans = 0\n",
    "        for i, c in enumerate(year):\n",
    "            cnt += c\n",
    "            if cnt > max_cnt:\n",
    "                max_cnt = cnt\n",
    "                ans = i\n",
    "        return 1950+ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        if len(logs) == 1:\n",
    "            return logs[0][0]\n",
    "\n",
    "        res = logs[0][0]\n",
    "        logs = sorted(logs, key = lambda x: x[0], reverse = True) \n",
    "\n",
    "        cnt, ans = 0, 0\n",
    "        for i in range(len(logs) - 1):\n",
    "            for  j in range(i+1, len(logs)):\n",
    "                if logs[i][0] >= logs[j][0] and logs[i][0] < logs[j][1]:\n",
    "                    cnt += 1\n",
    "                    \n",
    "            if cnt and cnt >= ans:\n",
    "                ans = cnt\n",
    "                res = logs[i][0]\n",
    "            cnt = 0\n",
    "\n",
    "        return res if ans else min(logs[-1][0], res)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        born=[]\n",
    "        dead=[]\n",
    "        for i in logs:\n",
    "            born.append(i[0])\n",
    "            dead.append(i[1])\n",
    "        b=0\n",
    "        for i in range(min(born),max(dead)):\n",
    "            a=0\n",
    "            for j in range(len(logs)):\n",
    "                if born[j]<=i<dead[j]:\n",
    "                    a+=1\n",
    "            if b<a:\n",
    "                b=a\n",
    "                ans=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        base_year = 1950\n",
    "        people = [0]*101\n",
    "        for i in logs:\n",
    "            people[i[0]-base_year] += 1\n",
    "            people[i[1]-base_year] -= 1\n",
    "        ans = m = current = 0\n",
    "        for i in range(len(people)):\n",
    "            current += people[i]\n",
    "            if current > m:\n",
    "                m, ans = current, base_year + i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        cnt = [0] * 3000\n",
    "        for start, end in logs:\n",
    "            for i in range(start, end):\n",
    "                cnt[i] += 1\n",
    "        m = max(cnt)\n",
    "        return next(i for i in range(3000) if cnt[i] == m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        cnt = Counter()\n",
    "        for b, d in logs:\n",
    "            for i in range(b, d):\n",
    "                cnt[i] += 1\n",
    "\n",
    "        return max([k for k in cnt], key=lambda t:(cnt[t], -t))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        delta = [0] * (2050 - 1950 + 1)\n",
    "        offset = 1950\n",
    "        for b, d in logs:\n",
    "            delta[b - offset] += 1\n",
    "            delta[d - offset] -= 1\n",
    "        mx = 0\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        for i in range(101):\n",
    "            cur += delta[i]\n",
    "            if cur > mx:\n",
    "                mx = cur\n",
    "                ans = i \n",
    "        return ans + offset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        p = [0] * 101\n",
    "        for start, end in logs:\n",
    "            p[start-1950] += 1\n",
    "            p[end-1950] -= 1\n",
    "        mx = ans = 0\n",
    "        for i, n in enumerate(accumulate(p)):\n",
    "            if n > mx:\n",
    "                mx, ans = n, i\n",
    "        return ans + 1950"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        pre=[0]*2051\n",
    "        p=[0]*2051\n",
    "        for b,d in logs:\n",
    "            for i in range(b,d):\n",
    "                p[i]+=1\n",
    "        maxY=1950\n",
    "        for i in range(1050,2051):\n",
    "            if p[maxY]<p[i]:\n",
    "                maxY=i\n",
    "        return maxY"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        populations=[]\n",
    "        for l in logs:\n",
    "            for k in range(l[0],l[1]):\n",
    "                populations.append(k)\n",
    "        c=Counter(populations)\n",
    "        c_tuple=[]\n",
    "        for i in c:\n",
    "            c_tuple.append((i,c[i]))\n",
    "        c_tuple.sort(key=lambda x:(x[1],-x[0]))\n",
    "        return c_tuple[-1][0]\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        year_to_population = defaultdict(int)\n",
    "\n",
    "        max_population = float(\"-inf\") # bigger\n",
    "        min_year = float('inf') # smaller\n",
    "\n",
    "        for start, end in logs:\n",
    "            for year in range(start, end):\n",
    "                year_to_population[year] += 1\n",
    "\n",
    "        for year, population in year_to_population.items():\n",
    "            if population > max_population or (population == max_population and year < min_year):\n",
    "                max_population = population\n",
    "                min_year = year\n",
    "        \n",
    "        return min_year\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        cha = [0 for i in range(105)]\n",
    "        for b,d in logs:\n",
    "            cha[b-1950] += 1\n",
    "            cha[d - 1950] -= 1\n",
    "        nian = 0\n",
    "        maxs = 0\n",
    "        pre = 0\n",
    "        for i in range(105):\n",
    "            if pre + cha[i] > maxs:\n",
    "                maxs = pre + cha[i]\n",
    "                nian = i + 1950\n",
    "            pre = cha[i] + pre\n",
    "        return nian"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        maxx= max(i[1] for i in logs)\n",
    "        minn=min(i[0] for i in logs)\n",
    "        list1=[]\n",
    "        list2=[]\n",
    "        for i in range(minn,maxx+1):\n",
    "            count=0\n",
    "            for j in range(len(logs)):\n",
    "                \n",
    "                if logs[j][0]<=i and i<logs[j][1]:\n",
    "                    count+=1\n",
    "            list2.append([i,count])\n",
    "            count=0\n",
    "\n",
    "        final=sorted(list2,key=lambda x:(-x[1],x[0]))\n",
    "\n",
    "        \n",
    "        return final[0][0]\n",
    "        \n",
    "        \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        \n",
    "        dates=[]\n",
    "        for birth,death in logs:\n",
    "            dates.append((birth,1))\n",
    "            dates.append((death,-1))\n",
    "        dates.sort()\n",
    "        person=max_person=max_year=0\n",
    "        for year,pp in dates:\n",
    "            person+=pp\n",
    "            if person>max_person:\n",
    "                max_person=person\n",
    "                max_year=year\n",
    "        return max_year"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "\n",
    "        sortLogs = sorted(logs, key=lambda x: x[0])\n",
    "\n",
    "        totalNumber = []\n",
    "        for i in range(len(sortLogs)):\n",
    "            if sortLogs[i][0] < sortLogs[i][1]:\n",
    "                totalNumber.append(1)\n",
    "\n",
    "            if i == 0:\n",
    "                continue\n",
    "\n",
    "            for index in range(i):\n",
    "                if sortLogs[index][1] > sortLogs[i][0]:\n",
    "                    totalNumber[-1] += 1\n",
    "        return sortLogs[totalNumber.index(max(totalNumber))][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        if len(logs) == 1:\n",
    "            return logs[0][0]\n",
    "\n",
    "        res = logs[0][0]\n",
    "        logs = sorted(logs, key = lambda x: x[0], reverse = True) \n",
    "\n",
    "        cnt, ans = 0, 0\n",
    "        for i in range(len(logs) - 1):\n",
    "            for  j in range(i+1, len(logs)):\n",
    "                if logs[i][0] >= logs[j][0] and logs[i][0] < logs[j][1]:\n",
    "                    cnt += 1\n",
    "                    print(logs[i], cnt)\n",
    "            if cnt and cnt >= ans:\n",
    "                ans = cnt\n",
    "                res = logs[i][0]\n",
    "            cnt = 0\n",
    "\n",
    "        return res if ans else min(logs[-1][0], res)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        dict1 = {}\n",
    "        a = 0\n",
    "        ans = 9999\n",
    "        for i in logs:\n",
    "            for x in range(i[0],i[1]):\n",
    "                if x in dict1:\n",
    "                    dict1[x] +=1\n",
    "                else:\n",
    "                    dict1[x] = 1\n",
    "        for k,v in dict1.items():\n",
    "            if v >a :\n",
    "                a = v\n",
    "                ans = k\n",
    "            elif v == a:\n",
    "                ans = min(ans,k)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        delta = [0] * 101\n",
    "        a = 1950\n",
    "        for i, j in logs:\n",
    "            delta[i - a] += 1\n",
    "            delta[j - a] -= 1\n",
    "        mx = 0\n",
    "        ans = 0\n",
    "        people = 0\n",
    "        for i in range(101):\n",
    "            people += delta[i]\n",
    "            if people > mx:\n",
    "                mx = people\n",
    "                ans = i\n",
    "        return ans + a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        num, res = 0, 0\n",
    "        dic = {}\n",
    "        for i,j in logs:\n",
    "            for k in range(i,j):\n",
    "                if k in dic:\n",
    "                    dic[k] += 1\n",
    "                else:\n",
    "                    dic[k] = 1\n",
    "                if dic[k] > num:\n",
    "                    res, num = k, dic[k]\n",
    "                elif dic[k] == num and res > k:\n",
    "                    res = k\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        if len(logs) == 1:\n",
    "            return logs[0][0]\n",
    "\n",
    "        res = logs[0][0]\n",
    "        logs = sorted(logs, key = lambda x: x[0], reverse = True) \n",
    "\n",
    "        cnt, ans = 0, 0\n",
    "        for i in range(len(logs) - 1):\n",
    "            for  j in range(i+1, len(logs)):\n",
    "                if logs[i][0] >= logs[j][0] and logs[i][0] < logs[j][1]:\n",
    "                    cnt += 1\n",
    "                    \n",
    "            if cnt and cnt >= ans:\n",
    "                ans = cnt\n",
    "                res = logs[i][0]\n",
    "            cnt = 0\n",
    "\n",
    "        return res if ans else min(logs[-1][0], res)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        cnt = [0] * 101\n",
    "        for l in logs:\n",
    "            for i in range(l[0], l[1]):\n",
    "                cnt[i-1950] += 1\n",
    "        for i, c in enumerate(cnt):\n",
    "           if c == max(cnt):\n",
    "               return i + 1950"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        population_dict = {}\n",
    "    \n",
    "        # Update the population_dict based on the logs\n",
    "        for birth, death in logs:\n",
    "            for year in range(birth, death):  \n",
    "                if year in population_dict:\n",
    "                    population_dict[year] += 1\n",
    "                else:\n",
    "                    population_dict[year] = 1\n",
    "        \n",
    "        # Find the year with the maximum population\n",
    "        max_population_year = min_year = 2050\n",
    "        max_population = 0\n",
    "        for year, population in population_dict.items():\n",
    "            if (population > max_population) or (population == max_population and year < max_population_year):\n",
    "                max_population = population\n",
    "                max_population_year = year\n",
    "        \n",
    "        return max_population_year"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        if len(logs) == 1:\n",
    "            return logs[0][0]\n",
    "\n",
    "        res = logs[0][0]\n",
    "        logs = sorted(logs, key = lambda x: x[0], reverse = True) \n",
    "\n",
    "        cnt, ans = 0, 0\n",
    "        for i in range(len(logs) - 1):\n",
    "            for  j in range(i+1, len(logs)):\n",
    "                if logs[i][0] >= logs[j][0] and logs[i][0] < logs[j][1]:\n",
    "                    cnt += 1\n",
    "                    \n",
    "            if cnt and cnt >= ans:\n",
    "                ans = cnt\n",
    "                res = logs[i][0]\n",
    "            cnt = 0\n",
    "\n",
    "        return res if ans else min(logs[-1][0], res)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        l1 = []\n",
    "        for i in range (len(logs)):\n",
    "            l1.append(logs[i][0])\n",
    "            l1.append(logs[i][1])\n",
    "        x1 = min(l1)\n",
    "        x2 = max(l1)\n",
    "        l2 = [0] * (x2 - x1)\n",
    "        for i in range (len(logs)):\n",
    "            for k in range (logs[i][0] - x1, logs[i][1] - x1):\n",
    "                l2[k] += 1\n",
    "        return l2.index(max(l2)) + x1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        dic={x:0 for x in range(1950,2051)}\n",
    "        for i in logs:\n",
    "            for k,v in dic.items():\n",
    "                if k>=i[0] and k<i[1]:\n",
    "                    dic[k]+=1\n",
    "        return max(dic,key=dic.get)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        计数 = [0]*101\n",
    "        for i, j in logs:\n",
    "            计数[i-1950] += 1\n",
    "            计数[j-1950] -= 1\n",
    "        最多人口 = 0\n",
    "        人口 = 0\n",
    "        年份 = 0\n",
    "        for i,j in enumerate(计数):\n",
    "            人口 += j\n",
    "            if 人口 > 最多人口:\n",
    "                最多人口 = 人口\n",
    "                年份 = i + 1950\n",
    "        return 年份"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        delta=[0]*101\n",
    "        offset=1950           #起始年份与起始下标\n",
    "        for b,d in logs:\n",
    "            delta[b-offset]+=1\n",
    "            delta[d-offset]-=1\n",
    "        mx=0                  #人口数量最大值\n",
    "        res=0                 #最大值对应的最小下标\n",
    "        curr=0                #每一年的人口数量\n",
    "        for i in range(101):\n",
    "            curr+=delta[i]\n",
    "            if curr>mx:\n",
    "                mx=curr\n",
    "                res=i\n",
    "        return res+offset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        delta = [0] * 101   # 变化量\n",
    "        offset = 1950   # 起始年份与起始下标之差\n",
    "        for b, d in logs:\n",
    "            delta[b-offset] += 1\n",
    "            delta[d-offset] -= 1\n",
    "        mx = 0   # 人口数量最大值\n",
    "        res = 0   # 最大值对应的最小下标\n",
    "        curr = 0   # 每一年的人口数量\n",
    "        # 前缀和\n",
    "        for i in range(101):\n",
    "            curr += delta[i]\n",
    "            if curr > mx:\n",
    "                mx = curr\n",
    "                res = i\n",
    "        return res + offset   # 转回对应的年份"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        dates = []\n",
    "        for birth,death in logs:\n",
    "            dates.append((birth,1))\n",
    "            dates.append((death,-1))\n",
    "        dates.sort()\n",
    "        population = max_population = max_year = 0\n",
    "        for year,change in dates:\n",
    "            population += change\n",
    "            if population > max_population:\n",
    "                max_population = population\n",
    "                max_year = year\n",
    "        return max_year"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        dates = []\n",
    "        for birth, death in logs:\n",
    "            dates.append((birth, 1))\n",
    "            dates.append((death, -1))\n",
    "            \n",
    "        dates.sort()\n",
    "        population = max_population = max_year = 0\n",
    "        for year, change in dates:\n",
    "            population += change\n",
    "            if population > max_population:\n",
    "                max_population = population\n",
    "                max_year = year\n",
    "        \n",
    "        return max_year\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        n = len(logs)\n",
    "        births = []\n",
    "        deaths = []\n",
    "        for birth, death in logs:\n",
    "            births.append(birth)\n",
    "            deaths.append(death)\n",
    "        births.sort()\n",
    "        deaths.sort()\n",
    "        maxPop = 0\n",
    "        tmpPop = 0\n",
    "        res = 0\n",
    "        p1 = p2 = 0\n",
    "\n",
    "        while p1 < n and p2 < n:\n",
    "            if births[p1] < deaths[p2]:\n",
    "                tmpPop += 1\n",
    "                p1 += 1\n",
    "            else:\n",
    "                tmpPop -= 1\n",
    "                p2 += 1\n",
    "            if tmpPop > maxPop:\n",
    "                maxPop = tmpPop\n",
    "                res = births[p1-1]\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        dic = {year : 0 for year in range(1950, 2050)}\n",
    "        for birthday, deathday in logs:\n",
    "            for i in range(birthday, deathday):\n",
    "                dic[i] += 1\n",
    "        return min(key for key, value in dic.items() if value == max(i for i in dic.values()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        d = [0] * 101\n",
    "        for log in logs:\n",
    "            d[log[0] - 1950] += 1\n",
    "            d[log[1] - 1950] -= 1\n",
    "        \n",
    "        s, res, cnt = 0, 0, 0\n",
    "        for i in range(100):\n",
    "            s += d[i]\n",
    "            if s > cnt:\n",
    "                cnt = s\n",
    "                res = i\n",
    "        return res + 1950"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        delta = [0] * 101\n",
    "        yrOffset = 1950\n",
    "        for b, d in logs:\n",
    "            delta[b - yrOffset] += 1\n",
    "            delta[d - yrOffset] -= 1\n",
    "        ret, maxCnt = 0, 0\n",
    "        cur = 0\n",
    "        for i, cnt in enumerate(delta):\n",
    "            cur += cnt \n",
    "            if cur > maxCnt:\n",
    "                ret, maxCnt = i, cur \n",
    "        return ret + yrOffset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        dict1 = {i:0 for i in range(1950,2051)}\n",
    "        for i in logs:\n",
    "            for j in range(i[0],i[1]):\n",
    "                dict1[j]+=1\n",
    "        return list(dict1.values()).index(max(dict1.values()))+1950"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        delta = [0 for _ in range(101)]\n",
    "        for b, d in logs:\n",
    "            delta[b - 1950] += 1\n",
    "            delta[d - 1950] -= 1\n",
    "        cur = 0\n",
    "        max_pop = 0\n",
    "        for i in range(101):\n",
    "            cur += delta[i]\n",
    "            if cur > max_pop:\n",
    "                max_pop = cur\n",
    "                ans = 1950 + i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        计数 = [0]*101\n",
    "        for i, j in logs:\n",
    "            计数[i-1950] += 1\n",
    "            计数[j-1950] -= 1\n",
    "        最多人口 = 0\n",
    "        人口 = 0\n",
    "        年份 = 0\n",
    "        for i,j in enumerate(计数):\n",
    "            人口 += j\n",
    "            if 人口 > 最多人口:\n",
    "                最多人口 = 人口\n",
    "                年份 = i\n",
    "        return 年份 + 1950"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        ans = {}\n",
    "        for l in logs:\n",
    "            s = l[0]\n",
    "            e = l[-1]\n",
    "            for i in range(s,e):\n",
    "                if i not in ans:\n",
    "                    ans[i] = 1\n",
    "                else:\n",
    "                    ans[i] += 1\n",
    "\n",
    "        ans = sorted(ans.items(),key=lambda x:x[1],reverse=True)\n",
    "        most = ans[0][1]\n",
    "        b = ans[0][0]\n",
    "        for a in ans:\n",
    "            if a[1] == most:\n",
    "                if a[0] < b:\n",
    "                    b = a[0]\n",
    "            else:\n",
    "                break\n",
    "        return b\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        delta = [0] * 101   # 变化量\n",
    "        offset = 1950   # 起始年份与起始下标之差\n",
    "        for b, d in logs:\n",
    "            delta[b-offset] += 1\n",
    "            delta[d-offset] -= 1\n",
    "        mx = 0   # 人口数量最大值\n",
    "        res = 0   # 最大值对应的最小下标\n",
    "        curr = 0   # 每一年的人口数量\n",
    "        # 前缀和\n",
    "        for i in range(101):\n",
    "            curr += delta[i]\n",
    "            if curr > mx:\n",
    "                mx = curr\n",
    "                res = i\n",
    "        return res + offset   # 转回对应的年份\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "\n",
    "        max_cnt = 0\n",
    "        ans = 0\n",
    "        for log in logs:\n",
    "            idx = 0\n",
    "            cur_cnt = 1\n",
    "            while idx < len(logs):\n",
    "                if(logs[idx][0] <= log[0] and logs[idx][1] - 1 >= log[0]):\n",
    "                    cur_cnt += 1\n",
    "                idx += 1\n",
    "            print(log, cur_cnt)\n",
    "            if(cur_cnt > max_cnt):\n",
    "                max_cnt = cur_cnt\n",
    "                ans = log[0]\n",
    "            if(cur_cnt == max_cnt and log[0] < ans):\n",
    "                ans = log[0]\n",
    "\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        if len(logs) == 1:\n",
    "            return logs[0][0]\n",
    "\n",
    "        res = logs[0][0]\n",
    "        logs = sorted(logs, key = lambda x: x[0], reverse = True) \n",
    "\n",
    "        cnt, ans = 0, 0\n",
    "        for i in range(len(logs) - 1):\n",
    "            for  j in range(i+1, len(logs)):\n",
    "                if logs[i][0] >= logs[j][0] and logs[i][0] < logs[j][1]:\n",
    "                    cnt += 1\n",
    "                    print(logs[i], cnt)\n",
    "            if cnt and cnt >= ans:\n",
    "                ans = cnt\n",
    "                res = logs[i][0]\n",
    "            cnt = 0\n",
    "\n",
    "        return res if ans else min(logs[-1][0], res)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumPopulation(self, logs: List[List[int]]) -> int:\n",
    "        if len(logs) == 1:\n",
    "            return logs[0][0]\n",
    "\n",
    "        res = logs[0][0]\n",
    "        logs = sorted(logs, key = lambda x: x[0], reverse = True) \n",
    "\n",
    "        cnt, ans = 0, 0\n",
    "        for i in range(len(logs) - 1):\n",
    "            for  j in range(i+1, len(logs)):\n",
    "                if logs[i][0] >= logs[j][0] and logs[i][0] < logs[j][1]:\n",
    "                    cnt += 1\n",
    "                    print(logs[i], cnt)\n",
    "            if cnt and cnt >= ans:\n",
    "                ans = cnt\n",
    "                res = logs[i][0]\n",
    "            cnt = 0\n",
    "\n",
    "        return res if ans else min(logs[-1][0], res)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
